package 链表;

/**
 * 92. 反转链表 II
 *
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *
 * 解题思路：
 * 1：定位反转区间：
 *找到链表中第 left-1 个节点（即反转区间的前一个节点），记为 pre。
 *找到链表中第 right+1 个节点（即反转区间的后一个节点），记为 succ。
 *
 * 2：反转区间链表：
 *反转从 left 到 right 的链表部分。
 * 3：重新连接链表：
 * 将 pre 的 next 指向反转后的链表头。
 * 将反转后的链表尾的 next 指向 succ。
 * 4：处理边界情况：
 *  如果 left == 1，说明需要从链表头部开始反转，此时 pre 为 null，直接返回反转后的链表头。
 */
public class L_92_1 {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right){
            return head;
        }

        // 创建一个虚拟节点，简化边界处理
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 找到left的前一个节点 left - 1
        ListNode pre = dummy;
        for (int i = 1; i < left; i++) {
            pre = pre.next;
        }
        // 反转left到right的部分
        ListNode curr = pre.next;
        ListNode prev = null;
        ListNode next = null;
        for (int i = left; i <=right; i++) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            // 下一位
            curr = next;
        }
        // 将原来的prev连接反转后的链表
        pre.next.next = curr;
        pre.next = prev; // 指向反转后的头节点

        return dummy.next;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
